package leetcode.code0378;

import leetcode.IDebug;

public class Solution implements IDebug {

	int m, n;

	int[][] matrix;

	public int kthSmallest(int[][] matrix, int k) {
		int ans = 0;
		this.matrix = matrix;
		this.m = matrix.length;
		this.n = matrix[0].length;
		int l = matrix[0][0], r = matrix[m - 1][n - 1];
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			int num = this.count(m - 1, 0, mid);
			if (num >= k) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	private int count(int x, int y, int ans) {
		if (x == -1 || y == n) {
			return 0;
		}
		int cur = 0;
		if (ans >= this.matrix[x][y]) {
			cur += x + 1 + this.count(x, y + 1, ans);
		} else {
			cur += this.count(x - 1, y, ans);
		}
		return cur;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
